package leetcode.dynamic;

import java.util.HashMap;
import java.util.HashSet;

public class Lc494_2 {

    HashMap<String, Integer> cache;
    //回溯
    public int findTargetSumWays(int[] nums, int target) {

        cache = new HashMap<>();
        return getSumWays(nums, target, 0, 0);
    }

    //getSumWays(idx, sum) = getSumWays(idx + 1, sum + nums[idx]) + getSumWays(idx + 1, sum - nums[idx])
    //getSumWays(idx, sum) 得到结果后可缓存起来，最终的结果就是getSumWays(0, 0)
    private int getSumWays(int[] nums, int target, int idx, int sum) {
        String key = idx + "_" + sum; //sum可能为负值，所以用hashmap缓存，string作为key
        if (cache.containsKey(key)) return cache.get(key);
        if (idx == nums.length) {
            cache.put(key, target == sum ? 1 : 0);
            return cache.get(key);
        }
        int cnt1 = getSumWays(nums, target, idx + 1, sum + nums[idx]);
        int cnt2 = getSumWays(nums, target, idx + 1, sum - nums[idx]);
        cache.put(key, cnt1 + cnt2);
        return cnt1 + cnt2;
    }


}
